The present invention relates to a memory controller and methods for enhancing write performance of a flash device and, more particularly, to a flash memory controller and methods for enhancing write performance by reducing write amplification of a flash memory device.
Many storage devices are based on flash memory: memory cards, USB flash keys and SSD's (solid-state disks) are examples of flash-based storage devices, also called flash disks. There are numerous advantages of flash disks over older magnetic disks: small size, light weight, low power consumption, fast access time and shock resistance are some of these advantages.
Flash memory is a type of electrically erasable programmable read-only memory (EEPROM). Flash memory cells are non-volatile, programmable, and may contain one or more bits of data. A flash memory has two main limitations: (i) cells may not be reprogrammed, except after erasing a large block of memory, and (ii) the memory can endure only a limited number of write and erase operations.
A NAND flash, the most common type of flash memory used for data storage is a page mode flash, in contrast to the older byte or word-mode NOR flash. The NAND flash's smallest addressable unit of memory is a page. Once addressed, individual bytes of the page are serially accessed on read, or serially loaded on write. Pages are not individually erasable and the smallest erasable unit of NAND flash memory is a block, which is much larger than a page. A typical size of a NAND flash page is 4 Kbytes (4224 bytes including 128 spare bytes), and a typical size of a NAND flash block is 256 KBytes or 512 KBytes, with 64 or 128 pages per block. A block is typically erased in 1.5 milliseconds. The time duration of a page write (including data serial download time) is typically 300 microseconds for 1-bit/cell flash and 900 microseconds for 2-bit/cell flash. Reading a page is significantly faster than writing.
In order to overcome flash limitations and provide flash devices with a disk-like interface, various data structures and algorithms have been described in the art. These have usually been implemented either as software that is part of a computer system, or more commonly, as part of a controller managing the flash device.
A comprehensive review of data structures and algorithms used for flash memories is given by Gal, E. and S. Toledo in the article “Algorithms and Data Structures for Flash Memories”, ACM Computing Surveys, 37(2):138-163, 2005. A common design of such a system for NAND flash is log-structured management: pages written to the media are recorded as if to a log, to sequentially free page locations, in their order of arrival. An early description and performance analysis of such a system is given by Wu, M. and W. Zwaenepoel, in the article “enVy, A non-volatile main memory storage system”, ACM SIGOPS Operating Systems Review vol. 28, no. 5, 86-97, December 1994, and also, though not in the context of flash memory, by Rosenblum, M. and J. K. Ousterhout, “The design and implementation of a log-structured file system”, ACM Transactions on Computer Systems; 10(1):26-52, February 1992.
Though variations may exist, a log-structured controller typically implements the following: the controller at all times guarantees that some minimum number d>0 of blocks are erased and free. At any point in time, the write destination of fresh data is the free space on one particular block, and fresh pages are written to that destination sequentially, in whatever order they arrive. If the page of the same logical page number was previously written, the controller invalidates the page's previous content, wherever it was written, making that page location superseded. In order to manage the invalidation of previous written content, the controller maintains a map of the current physical page number (PPN) of every logical page number (LPN), and a map of the space of all physical pages, showing which physical pages contain valid data and which are superseded. When the block, which is the current write destination, has had all its pages written, the controller selects another free block as the write destination.
Before doing so, the controller checks whether the number of free blocks has fallen below the minimum of d blocks. If so, the controller performs space reclamation. The space reclamation process includes: (i) selecting a free block as a write destination block; (ii) selecting a non-free block that contains some superseded pages and some valid pages, as a source block; (iii) copying all valid pages of the source non-free block to free pages of the destination block. Pages containing superseded data are not moved; and (iv) erasing the source block and adding it to the free block pool. The net effect is that pages containing superseded data on the source block are gained as free pages on the destination block. After completing space reclamation, the controller sets the first free page on the write destination block to be the new fresh data destination.
The space reclamation procedure described above performs flash writes (and reads) that may be called parasitic, as they are not fulfilling a read or write request initiated by an application. This effect of additional writes forced by the need to maintain the flash media is a general and unavoidable feature of flash algorithms, and is called in the art ‘write amplification’. If fresh data refers to data written to the flash by an application, then the write amplification is numerically defined as the ratio of the size of data actually written to the size of fresh data. An average write amplification of three, for example, means that for each fresh page of data, on average, three pages were actually written to the flash, two of which were written as part of the reclamation process. Write amplification of one is the minimum, and means no amplification. Write amplification is obviously detrimental to write performance. The effective performance of the flash device is cut by a factor equal to the average write amplification. For example, a flash device with a raw write rate of twelve megabytes per second, and a flash controller with write amplification of three, supports only four megabytes per second of application writes. Furthermore, write amplification is detrimental to the endurance of the flash device. Since the number of write/erase cycles of each flash block is limited, each write operation brings the device closer to ending its functional life. Therefore the lifetime of the flash device is effectively shortened by the write amplification factor. The space reclamation process determines the write amplification, and therefore the write performance of the media.
In order to demonstrate the write amplification effect, suppose the number of pages in a block is N, and the number of superseded pages in a block, selected to be freed by the space reclamation, is v. The number of page moves is therefore N-v, so that at the end of the copying, there remain v free pages in the write destination block, which may be used to write fresh data. The write amplification (which is defined as total number of writes divided by the writes performed by the reclamation process) is therefore N/v.
While ideally a block in which all pages are superseded can be found, in which case no parasitic page moves are necessary, this cannot be guaranteed. The best the controller can do, in the short-term, is to select the block with the smallest number of valid pages, in what may be called a greedy approach. The “greediness” of the algorithm must be tempered by conflicting wear-leveling and CPU load considerations. Long-term considerations may also justify deviating from a greedy approach, as this invention will demonstrate.
Flash data structures commonly define the formatted size of flash media to be less than the physical size of the flash devices which compose it, in what is called over-provisioning. Over-provisioning is the excess percentage of the formatted size available in physical flash space. For example, if flash devices of total size 64 GBytes are used to hold a media whose formatted size is 50 GBytes, over-provisioning is said to be 28% (64/50-1). There is a positive relation between over-provisioning and write performance in many flash algorithms, including log-structured ones. If the media is over provisioned by x (x is e.g., 100%), then the formatted media size is 1/(1+x) (in this example: ½) of the physical flash available, and at any point in time x/(1+x) (e.g. 50%) of the pages in a block are superseded on average. Greedy space reclamation will therefore guarantee write amplification no worse than (1+x)/x (e.g. 2). In practice, write amplification will be even lower (i.e. better), because the block with least valid pages will have fewer valid pages than the average.
It would be highly advantageous to have a flash memory controller that reduces write amplification, so as to improve write performance and prolong functional lifetime of a flash memory.